package 数据结构.排序.实例;
/**
 * 快速排序的时间复杂的为O(nlog n)
 * 快速排序是递归的方式进行的，执行的时候需要有一个栈来存储相应的数据。最大的赌鬼调用次数与递归树的深度一致
 * 所以做好的情况下空间复杂度为O(log n)最差的情况下控件的复杂度为O(n)
 *
 * 记录非次序的移动导致排序方法是不稳定的
 * 排序的过程中需要的就是定位表的下界和上界，所以适合用顺序结构很难使用链式结构
 *
 * */
public class $07_快速排序 {

    public static void min(int[]a,int i,int j){//采用的是二分的思想把数据进行分开处理
        if(i<j){
            int x=hi(a,i,j);//将数组一分为二，然后枢轴为x
            min(a,i,x-1);//将枢轴左边的数组进行快速排序
            min(a,x+1,j);//将枢轴右边的数组进行快速排序
        }
    }

    public static int hi(int[] a, int x, int y){
        //对于a中的数据进行一趟排序，并且返回枢轴的位置
        int sum=a[x];//此时a中的第一个数据作为枢轴
        int one=a[x];//枢轴的数据保存起来
        while (x<y){
            while(x<y&&one<=a[y]) --y;
            a[x]=a[y];//将比枢轴小的的记录都移动到低的一段
            while (x<y&&a[x]<=one) ++x;
            a[y]=a[x];//将比枢轴大的记录数据移动到高的一段
        }
        a[x]=sum;//两边的数据已经处理完毕，把枢轴数据放到相对的中间位置
        return x;//返回枢轴的位置
    }
}
